package com.github.kezhenxu94.playground.java.interview.netease;

import java.util.Scanner;

/**
 * 合唱团
 *
 * 有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生， 要求相邻两个学生的位置编号的差不超过 d，使得这 k
 * 个学生的能力值的乘积最大， 你能返回最大的乘积吗？ 输入描述:
 *
 * 每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)， 表示学生的个数，接下来的一行，包含 n
 * 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <=
 * d <= 50)。
 *
 *
 * 输出描述: 输出一行表示最大的乘积。
 *
 * 输入例子: 3 7 4 7 2 50
 *
 * 输出例子: 49
 * 
 * TODO
 * 
 * [Tags] Dynamic Programming
 *
 * @author ke.zhen.xu
 */
public class NetEaseChorus {

	public static void main(String[] args) {
		NetEaseChorus sol = new NetEaseChorus();
		Scanner scanner = new Scanner(System.in);
		int studentCount = scanner.nextInt();
		int[] abilities = new int[studentCount];
		for (int i = 0; i < studentCount; i++)
			abilities[i] = scanner.nextInt();
		int k = scanner.nextInt();
		int d = scanner.nextInt();
		System.out.println(sol.ability(abilities, k, d));
		scanner.close();
	}

	private long ability(int[] abilities, int k, int d) {
		long[][][] dp = new long[abilities.length][k][2];
		dp[0][0][0] = abilities[0];
		dp[0][0][1] = abilities[0];
		for (int i = 1; i < k; i++) {
			dp[0][i][0] = abilities[0];
			dp[0][i][1] = abilities[0];
		}

		for (int i = 1; i < abilities.length; i++) {
			dp[i][0][0] = dp[i - 1][0][0] > abilities[i] ? dp[i - 1][0][0] : abilities[i];
			dp[i][0][1] = dp[i - 1][0][1] < abilities[i] ? dp[i - 1][0][1] : abilities[i];
		}

		for (int i = 1; i < abilities.length; i++) {
			for (int j = 1; j < k; j++) {
				dp[i][j][0] = Math.max(dp[i][j][0],
						Math.max(dp[i - 1][j - 1][0] * abilities[i], dp[i - 1][j - 1][1] * abilities[i]));
				dp[i][j][1] = Math.min(dp[i][j][1],
						Math.min(dp[i - 1][j - 1][1] * abilities[i], dp[i - 1][j - 1][1] * abilities[i]));
			}
		}
		return Math.max(dp[abilities.length - 1][k - 1][0], dp[abilities.length - 1][k - 1][1]);
	}
}
